class Solution(object):
    def diagonalSort(self, mat):
        m = len(mat)
        n = len(mat[0])
        for k in range(1 - m, n):
            if k < 0:
                j = 0
                i = j - k
            else:
                i = 0
                j = i + k
            t = 0
            ans = []
            while i + t < m and j + t < n:
                ans.append(mat[i + t][j + t])
                t += 1
            ans.sort()
            t = 0
            while i + t < m and j + t < n:
                mat[i + t][j + t] = ans[t]
                t += 1
        return mat
